package com.future.light.hello.dt.chap03.sequencelist;

import java.util.Arrays;

/**
 * 单向的线性表
 * @author zhushijie
 *
 * @param <T>
 */
public class SequenceList<T> {
	private int size = 0; // 线性表内已存储元素的数量
	private Object[] eleArray; // 线性表的初始化空间

	/**
	 * 初始化操作，建立一个有一个元素的线性表。
	 */
	public SequenceList(int totalSize, T ele) {
		eleArray = new Object[totalSize];
		eleArray[0] = ele;
		size++;
	}

	/**
	 * 若线性表为空，返回true，否则返回false。
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 清除线性表内所有元素。
	 */
	public void clearList() {
		Arrays.fill(eleArray, null);
		size = 0;
	}

	/**
	 * 将线性表L中的第i个位置元素值返回给e。
	 * 
	 * @param i
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T getElem(int i) {
		if (i < 1 || i > size)
			throw new IndexOutOfBoundsException("线性表索引越界");
		return (T) eleArray[i - 1];
	}

	/**
	 * 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回-1表示失败。
	 * 
	 * @param ele
	 * @return
	 */
	public int locateElem(T ele) {
		for (int i = 0; i < size; i++) {
			if (ele.equals(eleArray[i]))
				return i+1;
		}
		return -1;
	}

	/**
	 * 在线性表L中的第index个位置插入新元素e。
	 * @param index
	 * @param ele
	 * @throws Exception
	 */
	public void insertEle(int index, T ele) throws Exception {
		if (index < 1 || index > size + 1)
			throw new IndexOutOfBoundsException("线性表索引越界");
		if (size == eleArray.length)
			throw new Exception("数组已满，不能再加入新元素");
		System.arraycopy(eleArray, index-1, eleArray, index, size - index + 1);
		eleArray[index - 1] = ele;
		size++;
	}

	/**
	 * 删除线性表L中第i个位置元素，并用e返回其值。
	 * @param index
	 * @return
	 */
	public T deleteEle(int index) {
		// 需测试
		if (index < 0 || index > size)
			throw new IndexOutOfBoundsException("线性表索引越界");
		T e = getElem(index);
		if (index < size)
			System.arraycopy(eleArray, index, eleArray, index - 1, size - index);
		eleArray[size-1] = null;
		size--;
		return e;
	}

	/**
	 * 返回线性表L的元素个数。
	 * @return
	 */
	public int getLength() {
		return size;
	}

	/**
	 * 输出线性表的所有数据元素。
	 */
	public String toString() {
		String str = null;
		if (size == 0)
			str = "[]";
		else {
			str = "[";
			for(Object o: eleArray){
				str += o + ", ";
			}
			str = str.substring(0, str.length() - 2) + "]";
		}
		return str;
	}

	public static void main(String[] args) throws Exception {
		SequenceList<Integer> s = new SequenceList<Integer>(10, 5);	//5
		s.insertEle(1, 4);	//4,5
		s.insertEle(2, 3);	//4,3,5
		s.insertEle(2, 2);	//4,2,3,5
		s.insertEle(5, 1);	//4,2,3,5,1
		s.insertEle(2, 7);	//4,7,2,3,5,1
		s.insertEle(7, 8);	//4,7,2,3,5,1,8
		s.insertEle(7, 9);	//4,7,2,3,5,1,9,8
		s.insertEle(7, 10);	//4,7,2,3,5,1,10,9,8
		s.insertEle(7, 6);	//4,7,2,3,5,1,6,10,9,8
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
		
		s.deleteEle(7);
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
		s.deleteEle(7);
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
		s.deleteEle(7);
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
		s.deleteEle(7);
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
		
		s.insertEle(7, 8);	//4,7,2,3,5,1,8
		s.insertEle(7, 9);	//4,7,2,3,5,1,9,8
		s.insertEle(7, 10);	//4,7,2,3,5,1,10,9,8
		s.insertEle(10, 6);	//4,7,2,3,5,1,10,9,8,6
		System.out.println("s.length is: " + s.getLength() +"\t\t s is: " + s.toString());
	}
}
